#include "dfs.h"

namespace eda_dream {
namespace graph {
namespace algorithm {

std::vector<std::vector<int> > directions = {
    { -1, 0 },
    { 0, -1 },
    { 1, 0 },
    { 0, 1 }
};

void DepthFirstSearch(Maze &maze) {
    std::vector<std::vector<int> > visited(maze.GetRow(), std::vector<int>(maze.GetCol(), 0));
    std::stack<Grid> dfs_ds;
    auto &table = maze.GetTable();
    Coord curr_x, curr_y, curr_step, next_x, next_y;
    Uint32 row = maze.GetRow(), col = maze.GetCol();

    Point src = maze.GetSource();
    dfs_ds.push(table[src.GetX()][src.GetY()]);
    while (!dfs_ds.empty()) {
        Grid &grid = dfs_ds.top();
        dfs_ds.pop();
        curr_x = grid.GetPoint().GetX();
        curr_y = grid.GetPoint().GetY();
        curr_step = grid.GetStep();

        if (table[curr_x][curr_y].GetGridType() == kDestination) {
            maze.printMaze();
            return;
        }
        else if (table[curr_x][curr_y].GetGridType() == kObstacle) {
            continue;
        }

        visited[curr_x][curr_y] = 1;

        for (auto &direction : directions) {
            next_x = curr_x + direction[0];
            next_y = curr_y + direction[1];

            if (next_x < 0 || next_x >= row || next_y < 0 || next_y >= col) {
                continue;
            }

            if (table[next_x][next_y].GetStep() == 0 || curr_step + 1 < table[next_x][next_y].GetStep()) {
                table[next_x][next_y].SetStep(curr_step + 1);
            }

            if (visited[next_x][next_y]) {
                continue;
            }

            dfs_ds.push(table[next_x][next_y]);
        }

    }

}


}
}
}